package com.eric.demo;

import com.google.common.collect.Lists;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author guangyin.zhang
 * @since 2020/1/16
 */
public class FindElement {

    public static void main(String[] args){
        FindElement findElement = new FindElement();
        findElement.find(new int[]{11,2,3,4,55,43,22}, 20);
    }

    /**
     * 使用HashMap，时间复杂度是O(n),空间复杂度：O(n)
     * @param nums
     * @param target
     * @return 没有找到的话数组中数值就是{-1,-1}
     */
    public int[] find(int[] nums, int target) {
        int[] result={-1, -1};
        Map<Integer, List<Integer>> map=new HashMap<Integer, List<Integer>>();
        for(int i=0;i<nums.length;i++) {
            if(map.containsKey(nums[i])){
                List<Integer> list = map.get(nums[i]);
                list.add(i);
                map.put(nums[i], list);
            }else{
                map.put(nums[i], Lists.newArrayList(i));
            }
        }

        for(int i=0;i<nums.length/2;i++) {
            int two = target-nums[i];

            if(map.containsKey(two)) {
                if(target!=2*two){
                    result[0] = i;
                    result[1] = map.get(two).get(0); //若多个相同的取第一个
                    return result;
                }else{
                    if(map.get(two).size() > 1){
                        result[0] = i;
                        result[1] = map.get(two).get(1);
                        return result;
                    }
                }
            }
        }
        return result;
    }

}
